package solutions.leetcode.easy;

import java.util.*;

/**
 * @author lizhidong
 *
 * <a href="http://leetcode-cn.com/problems/3sum/">15. 三数之和</a>
 */
public class Solution15 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> rst = new LinkedList<>();
        Set<Bean> tmpRst = new HashSet<>();
        int p = 0;
        while (p < nums.length - 2) {
            Set<Integer> set = new HashSet<>();
            for (int i = p + 1, len = nums.length; i < len; i++) {
                int other = -nums[p] - nums[i];
                if (set.contains(other)) {
                    tmpRst.add(new Bean(nums[p], other, nums[i]));
                }
                set.add(nums[i]);
            }
            p++;
        }
        for (Bean bean : tmpRst) {
            List<Integer> list = new LinkedList<>();
            list.add(bean.v1);
            list.add(bean.v2);
            list.add(bean.v3);
            rst.add(list);
        }
        return rst;
    }

    static class Bean {
        final int v1;
        final int v2;
        final int v3;

        public Bean(int v1, int v2, int v3) {
            this.v1 = v1;
            this.v2 = v2;
            this.v3 = v3;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Bean bean = (Bean) o;
            int[] t1 = new int[]{v1, v2, v3};
            int[] t2 = new int[]{bean.v1, bean.v2, bean.v3};
            Arrays.sort(t1);
            Arrays.sort(t2);
            for (int i = 0; i < 3; i++) {
                if (t1[i] != t2[i]) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public int hashCode() {
            int[] t = new int[]{v1, v2, v3};
            Arrays.sort(t);
            return Objects.hash(t[0], t[1], t[2]);
        }
    }

    public static void main(String[] args) {
        Solution15 solution = new Solution15();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(solution.threeSum(nums));
//        Bean bean1 = new Bean(0, 1, -1);
//        Bean bean2 = new Bean(-1, 1, 0);
//        System.out.println(bean1.equals(bean2));
    }
}